#pragma once
#include <cstring>
#include <string>
#include <sstream>
#include <iosfwd>

class BigInt
{
public:
	BigInt()
	{
		memset(m_data, 0, sizeof m_data);
	}

	BigInt(int v)
	{
		memset(m_data, 0, sizeof m_data);
		m_data[0] = v;
		normalize();
	}

	explicit BigInt(std::string str)
	{
		memset(m_data, 0, sizeof m_data);
		if(str.length() % 4 != 0)
		{
			std::string aa[] = {"000", "00", "0"};
			str = aa[str.length() % 4 - 1] + str;
		}
		int len = 0;
		while(str.length())
		{
			std::istringstream is(str.substr(str.length() - 4, 4));
			is >> m_data[len];
			len++;
			str.resize(str.length() - 4);
		}
	}

	BigInt& operator=(int v)
	{
		memset(m_data, 0, sizeof m_data);
		m_data[0] = v;
		normalize();
		return *this;
	}

	void operator += (int v)
	{
		m_data[0] += v;
		normalize();
	}

	void operator += (const BigInt &v)
	{
		for(int i = 0; i < s_size; i++)
		{
			m_data[i] += v.m_data[i];
		}
		normalize();
	}

	BigInt operator+(const BigInt &v)const
	{
		BigInt res = *this;
		res += v;
		return res;
	}

	BigInt operator-(const BigInt &v)const
	{
		int flag = 0;
		BigInt res;
		for(int i = 0; i < s_size; i++)
		{
			res.m_data[i] = m_data[i] - v.m_data[i] - flag;
			if(res.m_data[i] < 0)
			{
				res.m_data[i] += s_base;
				flag = 1;
			}
			else flag = 0;
		}
		return res;
	}

	void operator*=(int v) 
	{
		for(int i = 0; i < s_size; i++)
		{
			m_data[i] *= v;
		}
		normalize();
	}

	void operator*=(const BigInt &v)
	{
		int tmp_data[s_size];
		memcpy(tmp_data, m_data, sizeof m_data);
		memset(m_data, 0, sizeof m_data);
		for(int i = 0; i < s_size; i++)
		{
			for(int j = 0; i + j < s_size; j++)
			{
				m_data[i + j] += (tmp_data[i] * v.m_data[j]);
			}
			normalize();
		}
	}

	BigInt operator*(const BigInt &v) const
	{
		BigInt res = *this;
		res *= v;
		return res;
	}

	BigInt operator*(int v) const
	{
		BigInt res = *this;
		res *= v;
		return res;
	}

	friend BigInt operator*(int vi, const BigInt &vb)
	{
		BigInt res = vb;
		res *= vi;
		return res;
	}

	bool operator>(const BigInt &v)const
	{
		int i = s_size - 1;
		while(i >= 0 && m_data[i] == v.m_data[i])i--;
		return i >= 0 && m_data[i] > v.m_data[i];
	}
	
	bool operator<(const BigInt &v)const
	{
		int i = s_size - 1;
		while(i >= 0 && m_data[i] == v.m_data[i])i--;
		return i >= 0 && m_data[i] < v.m_data[i];
	}
	
	bool operator>=(const BigInt &v)const
	{
		int i = s_size - 1;
		while(i >= 0 && m_data[i] == v.m_data[i])i--;
		return i < 0 || m_data[i] >= v.m_data[i];
	}

	bool operator<=(const BigInt &v)const
	{
		int i = s_size - 1;
		while(i >= 0 && m_data[i] == v.m_data[i])i--;
		return i < 0 || m_data[i] <= v.m_data[i];
	}

	operator bool() const
	{
		int i = s_size - 1;;
		while(i >= 0)
		{
			if(m_data[i]) return true;
		}
		return false;
	}
	
	bool operator==(const BigInt &v)const
	{
		int i = s_size - 1;
		while(~i)
		{
			if(m_data[i] != v.m_data[i]) return false;
			i--;
		}
		return true;
	}

	bool operator != (int v) const
	{
		int i = s_size - 1;
		while(i && !m_data[i]) i--;
		return i >= 3 || m_data[2] * s_base * 1ll * s_base + m_data[1] * s_base + m_data[0] != v;
	}
	bool operator != (const BigInt &v)const
	{
		int i = s_size - 1;
		while(~i)
		{
			if(m_data[i] != v.m_data[i]) return true;
			i--;
		}
		return false;
	}
	friend std::istream &operator>>(std::istream &in, BigInt &v)
	{
		int t;
		in >> t;
		v = t;
		return in;
	}
	friend std::ostream &operator << (std::ostream &out, const BigInt &v)
	{
		int i = BigInt::s_size - 1;
		while(i >= 0 && !v.m_data[i]) i--;
		if(i < 0) i++;
		out << v.m_data[i];
		while(i)
		{
			i--;
			if(v.m_data[i] < 1000) out << 0;
			if(v.m_data[i] < 100) out << 0;
			if(v.m_data[i] < 10) out << 0;
			out << v.m_data[i];
		};
		return out;
	}
	friend inline void DivMod(const BigInt &d1, const BigInt &d2, BigInt &r1, BigInt &r2);

	void SetPower(int p)
	{
		memset(m_data, 0, sizeof m_data);
		m_data[p] = 1;
	}

	BigInt operator /= (int v)
	{
		int cur = 0, pos = s_size - 1, rpos = s_size - 1;
		while(pos >= 0)
		{
			while(pos >= 0)
			{
				cur = cur * s_base + m_data[pos];
				if(cur < v)
				{
					m_data[pos] = 0;
					pos--;
				}
				else break;
			}
			if(pos >= 0)
			{
				m_data[pos] = cur / v;
				cur %= v;
				pos--;
			}
		}
		return *this;
	}
	BigInt operator/(int v)const
	{
		BigInt res = *this;
		res /= v;
		return res;
	}
	int operator%(int v)const
	{
		int d = 1, res = 0;
		for(int i = 0; i < s_size; i++)
		{
			res = (res + m_data[i] * d) % v;
			d = (d * s_base) % v;
		}
		return res;
	}

	BigInt operator/(BigInt &a) const
	{
		BigInt res, rem;
		DivMod(*this, a, res, rem);
		return res;
	}

private:
	const static int s_base = 10000;
	const static int s_size = 30;
	int m_data[s_size];
	void normalize()
	{
		for(int i = 1; i < s_size; i++)
		{
			m_data[i] += m_data[i - 1] / s_base;
			m_data[i - 1] %= s_base;
		}
	}
};

inline void DivMod(const BigInt &d1, const BigInt &d2, BigInt &r1, BigInt &r2)
{
	int i = BigInt::s_size - 1, x, y;
	while(i >= 0  && !d1.m_data[i])i--;
	if(i < 0)
	{
		r1 = 0;
		r2 = d2;
		return;
	}
	BigInt pow_d, t;
	r1 = 0;
	r2 = d1;
	while(i >= 0)
	{
		pow_d.SetPower(i);
		x = 0;
		y = BigInt::s_base;
		while(y - x > 1)
		{
			int c = (y + x) / 2;
			t = pow_d * c * d2;
			if(t > r2)y = c;
			else x = c;
		}
		t = pow_d * x;
		r1 += t;
		r2 = d1 - d2 * r1;
		i--;
	}
}
